package LeetCode;

import TimeCounter.CglibProxy;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 *
 * 有效括号组合需满足：左括号必须以正确的顺序闭合。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：n = 3
 * 输出：["((()))","(()())","(())()","()(())","()()()"]
 * 示例 2：
 *
 * 输入：n = 1
 * 输出：["()"]
 *  
 *
 * 提示：
 *
 * 1 <= n <= 8
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/generate-parentheses
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Code22 {
    public List<String> generateParenthesis(int n) { // 使用递归方式解决这个问题，遇到不可的情况直接跳过
        ArrayList<String> answerList = new ArrayList<>();
        run(n,answerList,0,0,"");
        return answerList;
    }

    private void run(int n,List<String> answerList,int left,int right,String str){
        if (right > left)
            return;
        if (right == left && right == n){
            answerList.add(str);
            return;
        }
        if (left < n)
            run(n,answerList,left+1,right,str + "(");
        if (left > right)
            run(n,answerList,left,right+1,str + ")");
    }

    public List<String> generateParenthesis2(int n) { //2 使用 动态规划 解决问题
        // TODO 使用动态规划解决问题 https://leetcode-cn.com/problems/generate-parentheses/solution/zui-jian-dan-yi-dong-de-dong-tai-gui-hua-bu-lun-da/

        return null;
    }

    public static void main(String[] args) {
        Code22 proxy = new CglibProxy<Code22>().createProxy(new Code22());
        proxy.generateParenthesis(3);
        proxy.generateParenthesis(1);
    }
}
